//
//  38.二叉树的深度.swift
//  数据结构与算法
//
//  Created by ZERO on 2021/5/27.
//

import Foundation
/*
 题目：输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
 思路1：分治法，函数是求二叉树的最大深度，我们不必管函数具体是怎么实现的。
            所以最终结果为 max( 头结点左子树的最大深度, 头结点右子树的最大深度)+1
 思路2：bfs，记录树的层级
 */
func offer_38() {
    let root = BinaryTreeNode(4)
    root.leftNode = {
        let node = BinaryTreeNode(2)
        node.leftNode = BinaryTreeNode(1)
        node.rightNode = BinaryTreeNode(3)
        return node
    }()
    root.rightNode = {
        let node = BinaryTreeNode(6)
        node.leftNode = BinaryTreeNode(5)
        node.rightNode = BinaryTreeNode(7)
        return node
    }()
    print(Solution().treeDepth2(root))
}

fileprivate class Solution {
    func treeDepth1(_ pRoot: BinaryTreeNode<Int>?) -> Int {
        // write code here
        guard pRoot != nil else { return 0 }
        let leftDepth = treeDepth1(pRoot?.leftNode)
        let rightDepth = treeDepth1(pRoot?.rightNode)
        return max(leftDepth, rightDepth) + 1
    }
    
    func treeDepth2(_ pRoot: BinaryTreeNode<Int>?) -> Int {
        guard pRoot != nil else { return 0 }
        var level = 0
        var queue = [BinaryTreeNode<Int>]()
        queue.append(pRoot!)
        while !queue.isEmpty {
            var count = queue.count
            while count > 0 {
                let node = queue.removeFirst()
                if let left = node.leftNode {
                    queue.append(left)
                }
                if let right = node.rightNode {
                    queue.append(right)
                }
                count -= 1
            }
            level += 1
        }
        return level
    }
}
